#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/is-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*

 todo 是自己写出来的哦
 * */
bool isSubsequence(string s, string t) {
    if(s.size()==0)
        return true;
    if(t.size()==0)
        return false;

    int lowsize,hightsize;
    hightsize=t.size();
    lowsize=s.size();



    vector<vector<int>> dp(lowsize+1,vector<int>(hightsize+1,0));

    for (int i = 0; i <lowsize ; ++i) {
        if (s[i]==t[0])
            dp[i][0]=1;
        else if (i-1>=0)
            dp[i][0]= max(dp[i-1][0],0);
    }

    for (int i = 0; i <hightsize ; ++i) {

        if (s[0]==t[i])
            dp[0][i]=1;
        else if (i-1>=0)
            dp[0][i]= max(dp[0][i-1],0);

    }


    for (int i = 1; i <lowsize ; ++i) {
        for (int j = 1; j <hightsize ; ++j) {
            if (s[i]==t[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]= max(dp[i-1][j],dp[i][j-1]);

        }
    }


    return dp[lowsize-1][hightsize-1]==s.size();

}

//bool isSubsequence(string s, string t) {
//    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
//    for (int i = 1; i <= s.size(); i++) {
//        for (int j = 1; j <= t.size(); j++) {
//            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
//            else dp[i][j] = dp[i][j - 1];
//        }
//    }
//    if (dp[s.size()][t.size()] == s.size()) return true;
//    return false;
//}
